#include <bits/stdc++.h>

using namespace std;

// 数组的最小偏移量
// 给你一个由n个正整数组成的数组nums
// 你可以对数组的任意元素执行任意次数的两类操作：
// 如果元素是偶数，除以2
// 例如如果数组是[1,2,3,4]
// 那么你可以对最后一个元素执行此操作，使其变成[1,2,3,2]
// 如果元素是奇数，乘上2
// 例如如果数组是[1,2,3,4]
// 那么你可以对第一个元素执行此操作，使其变成[2,2,3,4]
// 数组的偏移量是数组中任意两个元素之间的最大差值
// 返回数组在执行某些操作之后可以拥有的最小偏移量
// 测试链接 : https://leetcode.cn/problems/minimize-deviation-in-array/

class Solution 
{
public:
    int minimumDeviation(vector<int>& nums) 
    {
        // 有序表可以查询最大值、最小值
        set<int> s;
        for(int x : nums)
        {
            s.insert(x % 2 == 0 ? x : 2 * x);
        }
        // 奇数会在奇数和偶数之间振荡，而偶数会先下降到奇数再进行振荡
        // 因此，可以先让所有奇数变成偶数，然后在振动的过程中求取最小偏移量
        int ans = *s.rbegin() - *s.begin();
        while(ans > 0 && *s.rbegin() % 2 == 0)
        {
            int max = *s.rbegin();
            s.erase(max);
            s.insert(max / 2);
            ans = min(ans, *s.rbegin() - *s.begin());
        }
        return ans;
    }
};